typedef char STDataType;

typedef struct stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void STInit(ST* ps)
{
	assert(ps);

	ps->a = NULL;
	ps->capacity = 0;
	ps->top = -1;  //top初始化位-1,top指向栈顶元素
}

void STPush(ST* ps, STDataType x)
{
	assert(ps);
	//扩容
	if (ps->top+1 == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* ret = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (ret == NULL)
		{
			perror("realloc");
			return;
		}
		ps->a = ret;
		ps->capacity = newcapacity;
	}

	ps->top++;
	ps->a[ps->top] = x;
}

void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top>=0);

	ps->top--;
}

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(ps->top>=0);

	return ps->a[ps->top];
}

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == -1;
}

int STSize(ST* ps)
{
	assert(ps);
	return ps->top+1;
}

void STDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a == NULL;
	ps->top = -1;
	ps->capacity = 0;
}

bool isValid(char* s) {
    ST p;
    STInit(&p);

    while(*s)
    {
        if(*s=='('||*s=='['||*s=='{')
        {
            STPush(&p,*s);
        }
        else
        {
            if(STEmpty(&p))
            return false;
            
            char ch=STTop(&p);
            STPop(&p);
            if(ch=='('&&*s!=')'||ch=='['&&*s!=']'||ch=='{'&&*s!='}')
            return false;
        }
        s++;
    }
    if(!STEmpty(&p))
    return false;

    return true;
}